package test.n00300;


public class Problem00323 {
    public static void main(String[] args) {
        //println("(()");
        //println(")()())");
        println("()(()");
    }

    public static void println(String s) {
        Solution ss = new Solution();
        System.out.println(s + "," + ss.longestValidParentheses(s));
    }

    private static class Solution {
        /**
         * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
         * <p>
         * 解题思路:
         * 栈
         *
         * @param s
         * @return
         */
        public int longestValidParentheses(String s) {
            int r = 0;
            int left = 0, right = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    left++;
                } else {
                    right++;
                }

                if (left == right) {
                    r = Math.max(r, 2 * right);
                } else if (right > left) {
                    left = right = 0;
                }
            }

            left = right = 0;
            for (int i = s.length() - 1; i >= 0; i--) {
                if (s.charAt(i) == '(') {
                    left++;
                } else {
                    right++;
                }

                if (left == right) {
                    r = Math.max(r, 2 * left);
                } else if (right < left) {
                    left = right = 0;
                }
            }
            return r;
        }
    }
}
